package 赎金信;

import java.util.HashMap;
import java.util.Map;

public class Solution2 {

    public boolean canConstruct(String ransomNote, String magazine) {
        // 采用哈希法(通过数组实现，因为我们很容易发现字符只需要26个，如果使用map，会增加hash计算)
        // 很容易想到，只需要判断 magazine 中是否存在 ransomNote 中的每一个字符（需要细节判断，一个元素只能使用一次）
        // 为了解决一个元素只能使用一次的问题，我们进一步使用 数组 集合解决问题，数组中的值就是字符在magazine 中出现的次数

        int[] count = new int[26];
        // 统计magazine中每个字符出现的次数，利用数组进行hash映射
        for (int i = 0; i < magazine.length(); i++) {
            char c = magazine.charAt(i);
            count[c-'a']++;
        }
        // 检查ransomNote中的每个字符是否能够映射到magazine中，且magzine中的每个字符最多使用一次
        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            int index = c - 'a';
            if ( count[index] != 0 )
                count[index]--;
            else
                return false;
        }
        return true;
    }
}